1. Field of the Invention
The present invention relates to a cryptography application circuit, and more particularly, to an inverse calculation circuit and inverse calculation method that is robust against a timing attack form of decryption and a differential power analysis (DPA) attack form of decryption, and a computer-readable non-transitory storage medium encoded with a computer-readable computer program code that implements the circuit or method.
2. Description of the Related Art
Cryptography was originally used in the defense and diplomatic fields to prevent compromise of national secrets. In the electronic age, financial institutions have long been using cryptography to manage electronic fund transfer. In addition, since the time when cryptography originally came into use in the economic and financial fields, it has been widely used for authentication of identification, encryption key management, digital signature, and identity verification.
Negligent management of decryption keys, predictability of passwords, or monitoring of keyboard inputs in communications networks may lead to a breach in security in the form of a decryption to an unauthorized person. Here, decryption indicates an activity in which an attempt is made to decrypt an encrypted text into a plaintext by determining a key that is originally used to encrypt the text when all information on the system such as the type of algorithm used for encrypting the plaintext and the operating system employed is known, but only the key used is unknown, as well as a method for attempting to decrypt an encrypted text into a plaintext only with the encrypted text (so called, “brute force” attack).
Common techniques for decryption include ciphertext-only attack, known plaintext attack, chosen plaintext attack, adaptively chosen plaintext attack, timing attack, and differential power analysis (DPA) attack.
The timing attack is a method in which it is determined whether the value of a predetermined bit is 0 or 1 using information related to the calculation time of an encryption algorithm, and based on the result, the encrypted text is decrypted. The DPA attack is a method in which according to the value of an input bit, the amount of power consumed by an encryption algorithm is analyzed, the bit values of a secret key are obtained, and then the encrypted text is decrypted. Various types of DPA attacks are summarized in “Introduction to Differential Power Analysis and Related Attacks”, by Kocher, et al, Cryptography Research. Inc, San Francisco, Calif., 1998.
Elliptic curve cryptography defined in binary finite field GF(2n) can be broken down into a cryptography using affine coordinates and a cryptography using projective coordinates.
The affine coordinates express a coordinate on an elliptic curve as (x,y) and the projective coordinates express a coordinate on an elliptic curve as (X,Y,Z). Accordingly, the relationship between a point on an elliptic curve in the affine coordinates and a point on an elliptic curve in the projective coordinates is expressed in the following Equation 1:
                              x          =                      X            Z                          ⁢                                  ⁢                  y          =                      Y            Z                                              (        1        )            
Among the type of calculations that can be performed on an elliptic curve are addition and doubling. Addition is used when two points being added are different, while doubling is used when two points being added are identical.
Calculation in the affine coordinates defined in a binary finite field (GF(2n)) is expressed in the following Equation 2:
                                                                        y                2                            +              xy                        =                                          x                3                            +                              ax                2                            +              b                                ,                                          ⁢                                    P              0                        =                          (                                                x                  0                                ,                                  y                  0                                            )                                ,                                    P              1                        =                          (                                                x                  1                                ,                                  y                  1                                            )                                ,                                          ⁢                      λ            =                                                            y                  0                                +                                  y                  1                                                                              x                  0                                +                                  x                  1                                                              ,                                    if              ⁢                                                          ⁢                              P                0                                      ≠                          P              1                                ,                                          ⁢                      λ            =                                          x                1                            +                                                y                  1                                                  x                  1                                                              ,                                    if              ⁢                                                          ⁢                              P                0                                      =                          P              1                                ,                                          ⁢                                    x              2                        =                          a              +                              λ                2                            +              λ              +                              x                0                            +                              x                1                                                    ⁢                                  ⁢                              y            2                    =                                                    (                                                      x                    1                                    +                                      x                    2                                                  )                            ⁢              λ                        +                          x              2                        +                          y              1                                                          (        2        )            
As shown in Equation 2, addition and doubling on an elliptic curve defined in a finite field (GF(2n)) are formed by calculations (that is, addition, squaring, multiplication, and inverse calculation) of finite fields (GF(2n)). The numbers and types of calculations required for performing addition and doubling calculations on each elliptic curve are provided in Table 1:
TABLE 1Types of calculationsNumber of calculationsPoint addition1I + 2M + 1SPoint doubling1I + 2M + 1SHere, I denotes the inverse calculation of finite field (GF(2n)), M denotes the multiplication of finite field (GF(2n)), and S denotes the squaring of finite field (GF(2n)). Since addition of finite field (GF(2n)) can be implemented by a bitwise XOR operation, the implementation of addition of finite field (GF(2n)) and the speed of the addition operation can be neglected and therefore the addition operation of finite field (GF(2n)) is not included in Table 1.
The inverse calculation of finite field (GF(2n)) is an operation that takes greater part in elliptic curve encryption than those of finite field (GF(2n)) multiplication and squaring. Accordingly, calculation in the projective coordinates that does not require inverse calculation is sometimes used for elliptic curve encryption. However, if addition and doubling on an elliptic curve using the affine coordinates become vulnerable to side channel attack, the stability of the elliptic curve encryption decreases.